We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation.

Further, this choice offα,β allows us to boundkfα,βk given that the ground cost functionc is boundedonX. The proof is given in Appendix C.4. B.3 LasttermconvergenceofSD With a slight change toSD, we can claim its last term convergence: In each iteration, check if S(αt,{βi}ni=1) . For simplicity, we omit the subscript of the Sinkhorn potentialfα,β and simply usef. This implies that 2f(x) exists and is bounded from above: x X,k 2f(x)k Lf, which concludestheproof.

We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation.

One can observe that the Sinkhorn potentials are not unique. Under Assumption A.2, for a fixed pair of Assume Assumptions A.2 and A.3, and denote In this section, we provide several lemmas to show the Lipschitz continuity (w.r.t. the underlying These lemmas will be used in the convergence analysis and the mean field analysis for SD . Please see the proof in Appendix C.3. It would be an interesting future work to remove this factor . W e note that the Lemma B.1 is strictly stronger than preexisting results: (1) Proposition 13 of Feydy et al. [2019] only shows that the dual potentials are continuous (not Lipschitz continuous) This is strictly weaker than (i) of Lemma B.1.

Computing a nonlinear interpolation between a set of probability measures is a foundational task across many disciplines.

We consider the problem of minimizing a functional over a parametric family of probability measures, where the parameterization is characterized via a push-forward structure. An important application of this problem is in training generative adversarial networks. In this regard, we propose a novel Sinkhorn Natural Gradient (SiNG) algorithm which acts as a steepest descent method on the probability space endowed with the Sinkhorn divergence. We show that the Sinkhorn information matrix (SIM), a key component of SiNG, has an explicit expression and can be evaluated accurately in complexity that scales logarithmically with respect to the desired accuracy. This is in sharp contrast to existing natural gradient methods that can only be carried out approximately. Moreover, in practical applications when only Monte-Carlo type integration is available, we design an empirical estimator for SIM and provide the stability analysis. In our experiments, we quantitatively compare SiNG with state-of-the-art SGD-type solvers on generative tasks to demonstrate its efficiency and efficacy of our method.

In this paper, we consider the problem of computing the barycenter of a set of probability distributions under the Sinkhorn divergence. This problem has recently found applications across various domains, including graphics, learning, and vision, as it provides a meaningful mechanism to aggregate knowledge. Unlike previous approaches which directly operate in the space of probability measures, we recast the Sinkhorn barycenter problem as an instance of unconstrained functional optimization and develop a novel functional gradient descent method named Sinkhorn Descent (SD). We prove that SD converges to a stationary point at a sublinear rate, and under reasonable assumptions, we further show that it asymptotically finds a global minimizer of the Sinkhorn barycenter problem. Moreover, by providing a mean-field analysis, we show that SD preserves the weak convergence of empirical measures. Importantly, the computational complexity of SD scales linearly in the dimension $d$ and we demonstrate its scalability by solving a $100$-dimensional Sinkhorn barycenter problem.